package com.isaiah.list;

import com.isaiah.heap.MaxHeap;

import java.util.Iterator;

/**
 * @Title: 顺序表的实现类
 * @Description: 顺序表底层使用数组存储元素
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/4/809:31
 */
public class ArrayList<E> implements Iterable<E>{
    /** 使用数组存储数据 */
    private E[] data;

    /** 记录当前数组data中实际存放的元素个数 */
    private int size;

    /**
     * 构造器，使用传入的容量创建顺序表
     * @param capacity
     */
    public ArrayList(int capacity) {
        this.data = (E[]) new Object[capacity];
        this.size = 0;
    }

    public ArrayList(E[] arr){
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < data.length; i++){
            data[i] = arr[i];
        }
        size = arr.length;
    }


    /**
     * 交换i和j索引位置上的元素
     * @param i
     * @param j
     */
    public void swap(int i, int j ){
        if (i < 0 || i >= size || j < 0 || j >= size){
            throw new IllegalArgumentException("index is illegal.");
        }
        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
    /**
     * 构造器，使用10作为默认容量创建顺序表
     */
    public ArrayList() {
        this(10);
    }

    /**
     * 获取顺序表中元素个数
     * @return
     */
    public int getSize(){
        return this.size;
    }

    /**
     * 获取顺序表的容量
     * @return
     */
    public int getCapacity(){
        return this.data.length;
    }

    /**
     * 判断顺序表是否为空
     * @return
     */
    public boolean isEmpty(){
        return this.size == 0;
    }


    /**
     * 在指定位置上添加元素
     * @param index
     * @param e
     */
    public void add(int index, E e){
        // 判断index参数是否合法
        if (index < 0 || index > this.size){
            throw new IllegalArgumentException("add failed, Require index >=0 and index < size");
        }
        // 判断数组是否已满
        /*
        if (this.size == this.data.length){
            throw new IllegalArgumentException("add failed, Array is full");
        }
        */
        // 如果当前data数组元素个数为整个数组容量时，以2倍的数组长度进行扩容
        if (this.size == this.data.length){
            resize(2 * this.data.length);
        }

        // 1.数组元素搬家
        for (int i = size - 1; i >= index;  i--){
            this.data[i + 1] = data[i];
        }
        // 2.添加元素到index位置
        this.data[index] = e;
        // 3.维护size加1
        size ++;
    }
    /**
     * 在所有元素前添加一个元素
     * @param e
     */
    public void addFirst(E e){
        this.add(0, e);
    }

    /**
     * 在所有元素后添加一个元素
     * @param e
     */
    public void addLast(E e){
        this.add(size, e);
    }

    /**
     * 查询顺序表中是否包含指定的元素
     * @param e
     * @return
     */
    public boolean contains(E e){
        for (int i = 0; i < size; i++){
            if (this.data[i] ==  e){
                return true;
            }
        }
        return false;
    }



    /**
     * 删除顺序表中index位置上的元素，返回删除的元素
     * @param index
     * @return
     */
    public E remove(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Remove failed. Index is illegal");
        }
        // 保存index位置上的元素
        E ret  =  this.data[index];
        // 把index位置之后的元素向前移动
        for (int i = index + 1; i < this.size; i++){
            this.data[i - 1] = this.data[i];
        }
        this.size --;
        this.data[size] = null;
        // 如果当前data数组元素个数为整个数组容量的1/2时，进行缩容
        if (this.size == this.data.length / 2){
            resize(this.data.length / 2);
        }
        return ret;
    }

    /**
     * 删除顺序表中第一个元素，返回删除的元素
     * @return
     */
    public E removeFirst(){
        return this.remove(0);
    }

    /**
     * 删除顺序表中最后一个元素，返回删除的元素
     * @return
     */
    public E removeLast(){
        return this.remove(this.size -1);
    }

    // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i] == e)
                return i;
        }
        return -1;
    }

    /**
     * 删除指定的元素
     * @param e
     */
    public boolean removeElement(E e){
        int index = this.find(e);
        if (index != -1){
            this.remove(index);

        }
        return false;
    }


    /**
     * 修改指定位置上的元素
     * @param index
     * @param e
     */
    public void set(int index, E e){
        // 判断参数是否合法
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        this.data[index] = e;
    }
    private void resize(int newCapacity) {
        // 1 创建一个新数组
        E[] newData = (E[]) new Object[newCapacity];
        // 2 把原来数组元素搬到新数组中
        for (int i = 0; i < this.size; i++){
            newData[i] = this.data[i];
        }
        // 3 让data指向新数组
        this.data = newData;
    }
    /**
     * 获取指定索引位置上的元素e
     * @param index
     * @return
     */
    public E get(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        return this.data[index];
    }

    @Override
    public String toString() {
        StringBuffer rs = new StringBuffer();
        rs.append(String.format("Array List: size = %d, capacity = %d\n", this.size, this.data.length));
        rs.append("[");
        for (int i = 0; i < this.size; i ++){
            rs.append(this.data[i]);
            if (i != size -1){
                rs.append(", ");
            }
        }
        rs.append("]");
        return rs.toString();
    }

    public E getLast() {
        return data[size];
    }

    public E getFirst() {
        return data[0];
    }


    @Override
    public Iterator<E> iterator() {
        return new IteratorImpl();
    }
    private class IteratorImpl<E> implements Iterator<E>{
        private int cursor;

        public IteratorImpl() {
            this.cursor = 0;
        }

        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        @Override
        public E next() {
            return (E) data[cursor++];
        }
    }
}
